package cc.rico.algorithm;

import org.apache.commons.lang3.ArrayUtils;

/**
 * @Author: Dell
 * @Date: 2018/12/6
 * @Description:希尔排序
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止.
 * 选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] items = new int[] {23, 22, 5, 6, -5, 90, 43, 90, 1, 34, 11, 45, 65, 87};
        PrintUtil.printArray(items);
        System.out.println("===========================================");

        int[] sortUpItems = sortUp(items);
//        PrintUtil.printArray(sortUpItems);
//        System.out.println("===========================================");

        int[] sortDownItems = sortDown(items);
        //PrintUtil.printArray(sortDownItems);
    }


    private static int[] sortUp(int[] items) {
        int[] result = new int[items.length];

        int score = 3;
        int gap = items.length / score;

        while (gap > 0) {
            int resultIndex = 0;

            for (int i = 0; i < gap; i++) {
                int[] subs = subArray(items, i, gap);
                subs = doInsertSortUp(subs);
                //PrintUtil.printArray(subs);

                for (int j = 0; j < subs.length; j++) {
                    result[resultIndex] = subs[j];
                    resultIndex++;
                }
            }

            gap = gap / score;
        }

        PrintUtil.printArray(result);
        return result;
    }

    private static int[] sortDown(int[] items) {
        int[] result = new int[items.length];

        int score = 3;
        int gap = items.length / score;

        while (gap > 0) {
            int resultIndex = 0;

            for (int i = 0; i < gap; i++) {
                int[] subs = subArray(items, i, gap);
                subs = doInsertSortDown(subs);
                //PrintUtil.printArray(subs);

                for (int j = 0; j < subs.length; j++) {
                    result[resultIndex] = subs[j];
                    resultIndex++;
                }
            }

            gap = gap / score;
        }

        PrintUtil.printArray(result);
        return result;
    }


    /**
     * 获取分组元素
     * @param items
     * @param start 开始下标
     * @param gap   分组间距
     * @return
     */
    private static int[] subArray(int[] items, int start, int gap) {
        int size = items.length / gap;
        int mod = items.length % gap;

        if(mod!=0 && start<mod) {
            size ++;
        }

        int[] subs = new int[size];

        for(int i=0; i<size; i++) {
            subs[i] = items[start+gap*i];
        }

        if(mod!=0 && start<mod) {
            subs[size-1] = items[items.length - mod + start];
        }

        return subs;
    }

    /**
     * 分组插入排序
     * @param items
     * @return
     */
    private static int[] doInsertSortUp(int[] items) {
        if(ArrayUtils.isEmpty(items)) {
            return null;
        }

        if(items.length == 1) {
            return items;
        }

        for(int i=1; i<items.length; i++) {
            int current = items[i];

            if(current > items[i-1]) {
                continue;
            }

            int insertIndex = i;
            for(int j=i-1; j>=0; j--) {
                if(current < items[j]) {
                   insertIndex = j;
                }
            }

            for(int k=i; k>insertIndex; k--) {
                items[k] = items[k-1];
            }
            items[insertIndex] = current;
        }

        return items;
    }

    private static int[] doInsertSortDown(int[] items) {
        if(ArrayUtils.isEmpty(items)) {
            return null;
        }

        if(items.length == 1) {
            return items;
        }

        for(int i=1; i<items.length; i++) {
            int current = items[i];

            if(current < items[i-1]) {
                continue;
            }

            int insertIndex = i;
            for(int j=i-1; j>=0; j--) {
                if(current > items[j]) {
                    insertIndex = j;
                }
            }

            for(int k=i; k>insertIndex; k--) {
                items[k] = items[k-1];
            }
            items[insertIndex] = current;
        }

        return items;
    }

}
